﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;


//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//L0 → L1 → … → Ln - 1 → Ln
//请将其重新排列后变为：
//
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
    void reorderList(ListNode* head)
    {
        // 处理边界情况
        if (head == nullptr || head->next == nullptr)
            return;
        ListNode* fast = head, * slow = head;
        // 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow 的落点在哪⾥）
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 2. 把 slow 后⾯的部分给逆序 - 头插法
        ListNode* head1 = new ListNode(0);
        ListNode* cur = slow->next;
        // 注意把两个链表给断开
        slow->next = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = head1->next;
            head1->next = cur;
            cur = next;
        }

        // 3. 合并两个链表 - 双指针
        ListNode* newhead = new ListNode(0);
        ListNode* cur1 = head, * cur2 = head1->next, * tail = newhead;
        while (cur1 || cur2)
        {
            // 先放第⼀个链表
            if (cur1)
            {
                tail->next = cur1;
                tail = tail->next;
                cur1 = cur1->next;
            }
            // 先放第二个链表
            if (cur2)
            {
                tail->next = cur2;
                tail = tail->next;
                cur2 = cur2->next;
            }
        }

        head = newhead->next;
        delete head1;
        delete newhead;

    }
};



 struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution
{
    struct compare
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        // 创建⼀个⼩根堆
        priority_queue<ListNode*, vector<ListNode*>, compare> heap;

        // 让所有的头结点进⼊⼩根堆
        for (auto l : lists)
            if (l) heap.push(l);

        // 合并 k 个有序链表
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while (!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if (t->next) heap.push(t->next);
        }

        prev = ret->next;
        delete ret;
        return prev;
    }
};


//给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
//
//k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
//
//你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        // 1. 先求出需要逆序多少组
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            n++;
            cur = cur->next;
        }

        n /= k;

        // 2. 重复 n 次：⻓度为 k 的链表的逆序即可
        ListNode* newhead = new ListNode(0);
        ListNode* tail = newhead;
        cur = head;
        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode* next = cur->next;
                cur->next = tail->next;
                tail->next = cur;
                cur = next;
            }
            tail = tmp;
        }

        // 把不需要翻转的接上
        tail->next = cur;
        cur = newhead->next;
        delete newhead;
        return cur;

    }
};


//你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        unordered_map<int, int> map;
        for (auto x : nums)
        {
            map[x]++;
        }

        for (auto& [x, y] : map)
        {
            if (y == 1)
            {
                return x;
                break;
            }
        }

        return -1;
    }
};

class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        // 依次去修改 ret 中的每⼀位
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (auto x : nums)
            {
                // 计算nums中所有的数的第 i 位的和
                if ((x >> i) & 1) sum++;
            }
            sum %= 3;
            if (sum == 1) ret |= (1 << i);
        }

        return ret;
    }
};

int main()
{

	return 0;
}